/*
 * VertexReplacement.java
 *
 * Created on February 22, 2007, 12:26 PM
 */

package edu.psu.bd.math.vertexreplacer;

//import cern.colt.matrix.*;
import java.awt.geom.Point2D;
import java.util.ArrayList;
import java.util.Iterator;
import java.util.Set;

import cern.colt.matrix.impl.DenseDoubleMatrix2D;
import cern.colt.matrix.impl.SparseDoubleMatrix2D;
import cern.colt.matrix.linalg.EigenvalueDecomposition;
import edu.uci.ics.jung.graph.Graph;
import edu.uci.ics.jung.graph.Vertex;
import edu.uci.ics.jung.graph.decorators.Indexer;
import edu.uci.ics.jung.graph.impl.UndirectedSparseGraph;
import edu.uci.ics.jung.utils.UserData;
import edu.uci.ics.jung.visualization.Layout;
import edu.uci.ics.jung.visualization.PluggableRenderer;
import edu.uci.ics.jung.visualization.SpringLayout;
import edu.uci.ics.jung.visualization.VisualizationViewer;


/**
 *
 * @author Joseph F. Pleso
 */
public class VertexReplacement {
    
    
    private ReplacementGraph[] r;
    private java.util.List<Graph> output;
    private int numGraphs;
    private VisualizationViewer currentVV;
    private Layout currentLayout;
    
    
    private java.util.List<Vertex[]> vertices;
    private java.util.List<Integer> diam;

    private int currentIteration;
    
    
    
    
    public VertexReplacement(java.util.List<UndirectedSparseGraph> l) {
        
        numGraphs = l.size() - 1;
        r = new ReplacementGraph[numGraphs];
        for (int i = 0; i < numGraphs; i++)
        {
            r[i] = new ReplacementGraph(l.get(i + 1));
        }
        
        output = new ArrayList<Graph>();

        vertices = new ArrayList<Vertex[]>();
        diam = new ArrayList<Integer>();
        

        

        output.add(l.get(0));
        initializeGraph(0);
    }
    

    private void initializeGraph(int last)
    {
        Graph g = output.get(last);
        SparseDoubleMatrix2D adjacency_matrix = new SparseDoubleMatrix2D(g.numVertices(),g.numVertices());
        SparseDoubleMatrix2D degree_matrix = new SparseDoubleMatrix2D(g.numVertices(),g.numVertices());
        
        Indexer indexer = Indexer.getAndUpdateIndexer(g);
        Vertex[] vs = new Vertex[g.numVertices()];
        for (int i = 0; i < g.numVertices(); i++)
        {
            vs[i] = (Vertex) indexer.getVertex(i);
        }
        
        vertices.add(vs);
        for (int i = 0; i < g.numVertices(); i++)
        {
           Set neighbors = vs[i].getNeighbors();
           Iterator iterator = neighbors.iterator();
           while (iterator.hasNext())
           {
               Vertex next = (Vertex) iterator.next();
               int j;
               for (j = 0; j < g.numVertices(); j++)
               {
                   if (next == vs[j])
                   {
                       adjacency_matrix.setQuick(i,j,1);
                       break;
                   }
                   
               }
           }
           degree_matrix.setQuick(i,i,vs[i].degree());
        }
        
        
        SparseDoubleMatrix2D laplacian_matrix = (SparseDoubleMatrix2D) degree_matrix.copy();
        for (int i = 0; i < g.numVertices(); i++)
            for (int j = 0; j < g.numVertices(); j++)
                if (i != j)
                    laplacian_matrix.setQuick(i,j,-1 * adjacency_matrix.getQuick(i,j));
        
        EigenvalueDecomposition projection = new EigenvalueDecomposition (laplacian_matrix);
        //Scaling happens here
        
        for (int i = 0; i < g.numVertices(); i++)
        {
            adjacency_matrix.setQuick(i,i,1);
        }

        DenseDoubleMatrix2D path_matrix = new DenseDoubleMatrix2D(g.numVertices(),g.numVertices());
        for (int i = 0; i < g.numVertices(); i++)
            for (int j = 0; j < g.numVertices(); j++)
                path_matrix.setQuick(i,j,adjacency_matrix.getQuick(i,j));
        
        
        Integer d = 1;
        while (path_matrix.size() != path_matrix.cardinality())
        {
            path_matrix = (DenseDoubleMatrix2D) path_matrix.zMult(adjacency_matrix, null);
            d++;
        }
        diam.add(d);
            

        Double scale = Main.DIMENSION.getWidth() / 2.0;
        for (int i = 0; i < g.numVertices(); i++)
        {

            DenseDoubleMatrix2D V = (DenseDoubleMatrix2D) projection.getV();
            Double maxX = 0.9 / maxEntry(V,1);
            Double maxY = 0.9 / maxEntry(V,2);
            vs[i].setUserDatum("x", ((Double) (V.getQuick(i,1) * maxX + 1.0)) * scale, UserData.SHARED);
            vs[i].setUserDatum("y", ((Double) (V.getQuick(i,2) * maxY + 1.0)) * scale, UserData.SHARED);

        }
    }
    
    /*private EigenvalueDecomposition decompose(DoubleMatrix2D l)
    {
        EigenvalueDecomposition projection = new EigenvalueDecomposition (l);
        DenseDoubleMatrix2D v = (DenseDoubleMatrix2D) projection.getV();
        for (int i = 1; i < v.rows(); i++)
        {
            for (int j = 0; j < i; j++)
            {
                if (l.getQuick(i,j) != 0)
                {
                    double junk = calcDistance(v.getQuick(i,1),v.getQuick(i,2),v.getQuick(j,1),v.getQuick(j,2));
                    l.setQuick(i,j,junk);
                    l.setQuick(j,i,junk);
                }
            }
         
            
            
        }
        return new EigenvalueDecomposition(l);
    }*/
    
    /*private Double calcDistance (double x0, double y0, double x1, double y1)
    {
        double dx = x0-x1;
        double dy = y0-y1;
        
        return Math.sqrt(dx*dx + dy*dy);
    }*/
    
    public Layout getLayout (){
        return currentLayout;
    }
    public VisualizationViewer getVV(){
        return currentVV;
    }
    
    public Double maxEntry (DenseDoubleMatrix2D m, int column)
    {
        Double maxValue = m.getQuick(0,column);
        Double minValue = maxValue;
        for (int i = 1; i < m.rows(); i++)
        {
            Double junk = m.getQuick(i,column);
            if (junk > maxValue)
                maxValue = junk;
            if (junk < minValue)
                minValue = junk;
        }
        if (minValue * -1 > maxValue)
            return minValue * -1;
        else
            return maxValue;
    }
    
    public void calcIteration(int i, PluggableRenderer pr){
        while (i >= output.size()) {
            getNext();
        }

        currentIteration = i;
        Graph g = output.get(i);
        boolean isRandom = Main.getIsRandom();

        int spring_length = ((Double)Main.DIMENSION.getWidth()).intValue();
        spring_length = spring_length / (4 * diam.get(i));
        
        //Constant is 30 for length
        SpringLayout sl =
                new SpringLayout (g,new SpringLayout.UnitLengthFunction(
                spring_length));
        sl.initialize(Main.DIMENSION);
        //sl.setRepulsionRange(10*spring_length/3);//default is 100
        sl.setStretch(1);//default is .7
        
        
        VisualizationViewer vv = new VisualizationViewer(sl,pr);
        Indexer indexer = Indexer.getAndUpdateIndexer(g);
        for (int j = 0; j < g.numVertices(); j++)
        {
            Vertex v = (Vertex) indexer.getVertex(j);
            Double x = (Double) v.getUserDatum("x");
            Double y = (Double) v.getUserDatum("y");
            if (!isRandom)
                sl.forceMove(v, x, y);
        }
        currentVV = vv;
        currentLayout = sl;
        
    }

    public void returnLayout ()
    {
        Graph g = output.get(currentIteration);
        Indexer indexer = Indexer.getAndUpdateIndexer(g);
        for (int i = 0; i < g.numVertices(); i++)
        {
            Vertex v = (Vertex) indexer.getVertex(i);
            Point2D point = currentLayout.getLocation(v);
            v.setUserDatum("x",point.getX(),UserData.SHARED);
            v.setUserDatum("y",point.getY(),UserData.SHARED);
        }
    }
    
    
    private void getNext(){
        
        Graph g = output.get(output.size()-1);
        g = (Graph) g.copy();

        int n = g.numVertices();
        
        Indexer i = Indexer.getAndUpdateIndexer(g);
        Vertex[] vertices = new Vertex[n];
        for (int j = 0; j < n; j++)
        {
            vertices[j] = (Vertex) i.getVertex(j);
        }
        
        for (int j = 0; j < n; j++)
        {
            for (int k = 0; k < numGraphs; k++)
            {
                if (vertices[j].degree() == r[k].getNumBoundary())
                {
                    r[k].replace(g,vertices[j]);
                    break;
                }
            }
        }
        
        
        output.add(g);
        initializeGraph(output.size()-1);
       
    }
    
   
}
